/**
 * @a https://leetcode.cn/problems/wildcard-matching/description/
 */

#include "../common.h"
class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, iStar_rec = -1, jStar_rec = -1;
        while(i < s.size()){
            if(j < p.size() && (s[i] == p[j] || p[j] == '?')){
                i++,j++;
            }
            else if(j < p.size() && p[j] == '*'){
                iStar_rec = i;
                jStar_rec = j++;
            }
            // * 匹配错误，回溯
            else if(iStar_rec >= 0 || jStar_rec >= 0)//任意一个为非负数均可
            {
                j = jStar_rec + 1;
                i = ++iStar_rec;
            }
            else return false;
        }
        // 现在 s 遍历完， 不一定正确，p可能没遍历完。由于 * 可以表示空字符所以可以消除后面没有用到的 *
        while(j < p.size() && p[j] == '*') {
            j++;
        }
        return j == p.size();
    }
};

// 第二次
class Solution {
public:
    bool isMatch(string s, string p)
    {
        int cur1 = 0, cur2 = 0;
        int sz1 = s.size(), sz2 = p.size();
        int s_rec_index = -1, p_rec_index = -1;
        while(cur1 < sz1){
            if(cur2 < sz2 && (s[cur1] == p[cur2] || p[cur2] == '?')){
                ++cur1, ++ cur2;
            }
            else if(cur2 < sz2 && p[cur2] == '*'){
                s_rec_index = cur1;
                p_rec_index = cur2++;
            }
            else if(s_rec_index != -1){
                cur1 = ++s_rec_index;
                cur2 = p_rec_index + 1;
            }
            else return false;
        }
        while(cur2 < sz2 && p[cur2] == '*') cur2++;

        return cur2 == sz2;
    }
};


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for(int i = 1; i < n + 1; i++) if(p[i - 1] == '*') dp[0][i] = dp[0][i - 1];

        for(int i = 1; i < m + 1; ++i){
            for(int j = 1; j < n + 1; ++j){
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?') dp[i][j] = dp[i - 1][j -1];
                else if(p[j - 1] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                // dp[i][j-1] 表示当前 j - 1 处星号不表示任何字符。
            }
        }
        return dp[m][n];
    }
};